package interview;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class lc148 {
    static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public static void main(String[] args) {

    }

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        List<ListNode> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            ListNode pre = head.next;
            head.next = null;
            head = pre;

        }
        list.sort((a, b) -> {
            return a.val - b.val;
        });
        ListNode ans = list.get(0);
        head = ans;
        for (int i = 1; i < list.size(); i++) {
            head.next = list.get(i);
            head = head.next;
        }
        return ans;
    }
}
